package day190804;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/4 上午 11:21
 */
public class SnapshotArray {
    List<TreeMap<Integer, Integer>> list = new ArrayList<>();
    int version = 0;

    public SnapshotArray(int length) {
        version = 0;
        for (int i = 0; i < length; i++) {
            TreeMap<Integer, Integer> map = new TreeMap<>();
            map.put(version, 0);
            list.add(map);
        }
    }

    public void set(int index, int val) {
        list.get(index).put(version, val);
    }

    public int snap() {
        int res = version;
        version++;
        return res;
    }

    public int get(int index, int snap_id) {
        TreeMap<Integer, Integer> map = list.get(index);
        return map.floorEntry(snap_id).getValue();
    }

    public static void main(String[] args) {
//        SnapshotArray snapshotArr = new SnapshotArray(3);
//        snapshotArr.set(0, 5);  // 令 array[0] = 5
//        snapshotArr.snap();  // 获取快照，返回 snap_id = 0
//        snapshotArr.set(0, 6);
//        int i = snapshotArr.get(0, 0);
        System.out.println(String.valueOf(Math.pow(10, 9) + 7));


    }

    public int ordinalOfDate(String date) {
        int sum = 0, m;
        String[] split = date.split("-");
        int year = Integer.parseInt(split[0]);
        int month = Integer.parseInt(split[1]);
        int day = Integer.parseInt(split[2]);
        if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
            m = 29;
        } else {
            m = 28;
        }
        switch (month) {
            case 1:
                sum = 0;
                break;
            case 2:
                sum = 31;
                break;
            case 3:
                sum = m + 31;
                break;
            case 4:
                sum = m + 31 + 31;
                break;
            case 5:
                sum = m + 31 + 31 + 30;
                break;
            case 6:
                sum = m + 31 + 31 + 30 + 31;
                break;
            case 7:
                sum = m + 31 + 31 + 30 + 31 + 30;
                break;
            case 8:
                sum = m + 31 + 31 + 30 + 31 + 30 + 31;
                break;
            case 9:
                sum = m + 31 + 31 + 30 + 31 + 30 + 31 + 31;
                break;
            case 10:
                sum = m + 31 + 31 + 30 + 31 + 30 + 31 + 31 + 30;
                break;
            case 11:
                sum = m + 31 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31;
                break;
            case 12:
                sum = m + 31 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30;
                break;
            default:
                break;
        }
        sum = sum + day;
        return sum;
    }

    public int numRollsToTarget(int d, int f, int target) {
        if (d <= 0) {
            return 0;
        }
        long[][] arr = new long[d + 1][f * d + 1];
        for (int i = 1; i <= f; i++) {
            arr[1][i] = 1;
        }
        for (int i = 2; i <= d; i++) {
            for (int j = i; j <= f * i; j++) {
                int temp = 1;
                while (temp <= f) {
                    if (temp <= j) {
                        arr[i][j] += arr[i - 1][j - temp];
                    }
                    temp++;
                }
            }
        }
        //输出结果
        // for (int i = d; i <= f * d; i++) {
        // sum += arr[d][i];
        // }
        if (target >= f * d + 1) {
            return 0;
        }

        return Math.toIntExact(arr[d][target] % 1000000007);
    }

    public int numRollsToTarget2(int number, int maxValue, int target) {
        if (number <= 0) {
            return 0;
        }
        int[][] probabilities = new int[2][number * maxValue + 1];
        //[2]代表用两个数组交替保存，[number*maxValue+1]是指点数为所在下标时，该点数出现的总次数。
        //probabilities[*][0]是没用的，只是为了让下标对应点数
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < number * maxValue; j++) {
                probabilities[i][j] = 0;
            }
        }

        for (int i = 1; i <= 6; i++) {
            probabilities[0][i] = 1;  //第一个骰子出现的情况
        }

        int flag = 0;
        for (int curNumber = 2; curNumber <= number; curNumber++) {   //当前是第几个骰子
            for (int i = 0; i < curNumber; i++) {
                probabilities[1 - flag][i] = 0;  //前面的数据清零
            }

            for (int i = curNumber; i <= curNumber * maxValue; i++) {
                for (int j = 1; j <= 6 && j <= i; j++) {
                    probabilities[1 - flag][i] += probabilities[flag][i - j];
                }
            }
            flag = 1 - flag;
        }


        return probabilities[flag][target];
    }

    public int numRollsToTarget3(int number, int maxValue, int target) {
        if (number <= 0) {
            return 0;
        }
        if (target > number * maxValue) {
            return 0;
        }
        int[][] probabilities = new int[2][number * maxValue + 1];
        //[2]代表用两个数组交替保存，[number*maxValue+1]是指点数为所在下标时，该点数出现的总次数。
        //probabilities[*][0]是没用的，只是为了让下标对应点数
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < number * maxValue; j++) {
                probabilities[i][j] = 0;
            }
        }

        for (int i = 1; i <= maxValue; i++) {
            probabilities[0][i] = 1;  //第一个骰子出现的情况
        }

        int flag = 0;
        for (int curNumber = 2; curNumber <= number; curNumber++) {   //当前是第几个骰子
            for (int i = 0; i < curNumber; i++) {
                probabilities[1 - flag][i] = 0;  //前面的数据清零
            }

            for (int i = curNumber; i <= curNumber * maxValue; i++) {
                for (int j = 1; j <= maxValue && j <= i; j++) {
                    probabilities[1 - flag][i] += probabilities[flag][i - j];
                }
            }
            flag = 1 - flag;
        }


        return probabilities[flag][target];
    }

    public int numRollsToTarget4(int d, int f, int target) {
        int[] a = new int[1050];
        a[0] = 1;
        for (int i = 1; i <= d; i++) {
            for (int j = 1; j <= f; j++) {
                for (int k = j; k <= target; k++) {
                    a[k] = (a[k] + a[k - j]) % 1000000007;
                }
            }
        }
        return a[target];
    }

}
